package com.bo.day20241119;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;

/**
 * 测试链接：https://leetcode.com/problems/number-of-islands/
 * 给定一个二维数组matrix，里面的值不是1就是0，
 * 上、下、左、右相邻的1认为是一片岛，
 * 返回matrix中岛的数量
 *
 * @Author: gpb
 * @Date: 2024/11/20 10:07
 * @Description:
 */
public class NumberOfIslands {

    public static void main (String[] args) {
        int[][] arr = {{1, 1, 0, 1}, {1, 0, 0, 0}, {0, 0, 1, 0}};
        System.out.println(arr.length);
        System.out.println(arr[0].length);
        int[] ar = new int[arr.length * arr[0].length];
        System.out.println(ar.length);
        ar[(arr.length - 1) * (arr[0].length) - 1] = 12131;
        System.out.println(ar[(arr.length - 1) * (arr[0].length) - 1]);
        // ===================================================================================
        int row = 0;
        int col = 0;
        char[][] board1 = null;
        char[][] board2 = null;
        char[][] board3 = null;
        long start = 0;
        long end = 0;

        row = 1000;
        col = 1000;
        board1 = generateRandomMatrix(row, col);
        board2 = copy(board1);
        board3 = copy(board1);

        System.out.println("感染方法、并查集(map实现)、并查集(数组实现)的运行结果和运行时间");
        System.out.println("随机生成的二维矩阵规模 : " + row + " * " + col);

        start = System.currentTimeMillis();
        System.out.println("感染方法的运行结果: " + numIslandsByInfection(board1));
        end = System.currentTimeMillis();
        System.out.println("感染方法的运行时间: " + (end - start) + " ms");

        start = System.currentTimeMillis();
        System.out.println("并查集(map实现)的运行结果: " + numIslandsByUnionFindDot(board2));
        end = System.currentTimeMillis();
        System.out.println("并查集(map实现)的运行时间: " + (end - start) + " ms");

        start = System.currentTimeMillis();
        System.out.println("并查集(数组实现)的运行结果: " + numIslands(board3));
        end = System.currentTimeMillis();
        System.out.println("并查集(数组实现)的运行时间: " + (end - start) + " ms");

        System.out.println();

        row = 10000;
        col = 10000;
        board1 = generateRandomMatrix(row, col);
        board3 = copy(board1);
        System.out.println("感染方法、并查集(数组实现)的运行结果和运行时间");
        System.out.println("随机生成的二维矩阵规模 : " + row + " * " + col);

        start = System.currentTimeMillis();
        System.out.println("感染方法的运行结果: " + numIslandsByInfection(board1));
        end = System.currentTimeMillis();
        System.out.println("感染方法的运行时间: " + (end - start) + " ms");

        start = System.currentTimeMillis();
        System.out.println("并查集(数组实现)的运行结果: " + numIslands(board3));
        end = System.currentTimeMillis();
        System.out.println("并查集(数组实现)的运行时间: " + (end - start) + " ms");
    }

    // 为了测试
    public static char[][] generateRandomMatrix (int row, int col) {
        char[][] board = new char[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                board[i][j] = Math.random() < 0.5 ? '1' : '0';
            }
        }
        return board;
    }

    // 为了测试
    public static char[][] copy (char[][] board) {
        int row = board.length;
        int col = board[0].length;
        char[][] ans = new char[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                ans[i][j] = board[i][j];
            }
        }
        return ans;
    }

    /**
     * 岛的数量
     * 解题思路：
     * 使用感染方式解题
     * 1.遍历二维数组，找到值为1的点，作为感染的起点，感染上下左右四个方向的1，直到没有 infection 为1 的点，此时一个岛已经感染完毕，
     *
     * @param board
     * @return
     */
    public static int numIslandsByInfection (char[][] board) {
        int islands = 0;
        for (int i = 0; i < board.length; i++) {
            for (int i1 = 0; i1 < board[i].length; i1++) {
                if (board[i][i1] == '1') {
                    islands++;
                    // 感染 感染上下左右四个方向的1,只要是1那就修改为2
                    infect(board, i, i1);
                }
            }
        }
        return islands;
    }

    private static void infect (char[][] board, int i, int i1) {
        // 边界条件, 防止数组越界 board[i][i1]!='1' 终止
        if (i < 0 || i >= board.length || i1 < 0 || i1 >= board[i].length || board[i][i1] != '1') {
            return;
        }
        // 感染,修改成2
        board[i][i1] = '2';
        // 上面感染
        infect(board, i - 1, i1);
        // 下面感染
        infect(board, i + 1, i1);
        // 左边感染
        infect(board, i, i1 - 1);
        // 右边感染
        infect(board, i, i1 + 1);
    }

    /**
     * 并查集解法
     * 使用对象代替1，使用并查集解题
     * 解题思路：
     * 只需要检测左边和上边是否是1，如果是1，则合并，合并后，左边和上边都是1，则合并后
     *
     * @param board
     * @return
     */
    public static int numIslandsByUnionFindDot (char[][] board) {
        int row = board.length;
        int col = board[0].length;
        // 创建一个二维数组，用来存储每个点的对象
        Dot[][] dots = new Dot[row][col];
        // 存储集合
        List<Dot> list = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            for (int i1 = 0; i1 < board[i].length; i1++) {
                // 创建对象
                if (board[i][i1] == '1') {
                    dots[i][i1] = new Dot();
                    list.add(dots[i][i1]);
                }
            }
        }
        // 创建并查集
        UnionFindDot<Dot> unionFind = new UnionFindDot(list);
        // 遍历矩阵,只需要检测自己的左边和上边是不是1即可，如果是1那就合并
        for (int i = 1; i < col; i++) {
            // 先检查左边是否是1，如果是1就合并
            // (0,1),(0,2),(0,3)...
            // 当前是不是1,和左边是不是1，如果是1，就合并，否则不用合并
            if (board[0][i] == '1' && board[0][i - 1] == '1') {
                unionFind.union(dots[0][i], dots[0][i - 1]);
            }
        }
        // 遍历矩阵,只需要检测自己的上边是否是1即可，如果是1就合并
        for (int i = 1; i < row; i++) {
            // 先检查上边是不是1，如果是1就合并
            // (1,0),(2,0),(3,0)...
            if (board[i][0] == '1' && board[i - 1][0] == '1') {
                unionFind.union(dots[i][0], dots[i - 1][0]);
            }
        }
        // 遍历矩阵,只需要检测自己的左边和上边是否是1即可，如果是1就合并
        for (int i = 1; i < row; i++) {
            for (int i1 = 1; i1 < col; i1++) {
                // 当前是不是1,和左边是不是1，如果是1，就合并，否则不用合并
                if (board[i][i1] == '1' && board[i][i1 - 1] == '1') {
                    unionFind.union(dots[i][i1], dots[i][i1 - 1]);
                }
                // 当前是不是1,和上边是不是1，如果是1，就合并，否则不用合并
                if (board[i][i1] == '1' && board[i - 1][i1] == '1') {
                    unionFind.union(dots[i][i1], dots[i - 1][i1]);
                }
            }
        }
        // 当前是不是1,和左边是不是1，如果是1，就合并，否则不用合并
        return unionFind.sets();
    }

    /**
     * 使用并查集解决
     * 解题思路：
     * 并查集使用数组实现
     * 公式：矩阵中的数据在并查集中的下标为：row * col + col
     * 1.创建一个并查集，并把所有的点都放入并查集中，并初始化每个点的父节点为自身，并初始化每个点的集合大小为1
     * 只需要检测左边和上边是否是1，如果是1，则合并，合并后，左边和上边都是1，则合并后
     *
     * @param board
     * @return
     */
    public static int numIslands (char[][] board) {
        UnionFind unionFind = new UnionFind(board);
        int row = board.length;
        int col = board[0].length;
        // 遍历矩阵,首先把第一列遍历,只需要检测左边是否是1，如果是1就合并
        for (int i = 1; i < col; i++) {
            if (board[0][i] == '1' && board[0][i - 1] == '1') {
                unionFind.union(0, i - 1, 0, i);
            }
        }
        // 遍历矩阵,首先把第一行遍历,只需要检测左边是否是1，如果是1就合并
        for (int i = 1; i < col; i++) {
            if (board[i][0] == '1' && board[i - 1][0] == '1') {
                unionFind.union(i - 1, 0, i, 0);
            }
        }
        for (int i = 1; i < row; i++) {
            for (int i1 = 1; i1 < col; i1++) {
                // 当前是不是1,和左边是不是1，如果是1，就合并，否则不用合并
                if (board[i][i1] == '1' && board[i][i1 - 1] == '1') {
                    unionFind.union(i, i1 - 1, i, i1);
                }
                // 当前是不是1,和上边是不是1，如果是1，就合并，否则不用合并
                if (board[i][i1] == '1' && board[i - 1][i1] == '1') {
                    unionFind.union(i - 1, i1, i, i1);
                }
            }
        }
        return unionFind.sets();
    }

    public static class UnionFind {
        // 父节点,下标计算公式：row * col + col
        int[] parent;
        // 集合大小
        int[] size;
        // 辅助数组
        int[] help;
        int sets;
        // 行长度
        int row;
        // 列长度
        int col;

        public UnionFind (char[][] board) {
            row = board.length;
            col = board[0].length;
            // 创建并查集
            parent = new int[row * col];
            size = new int[row * col];
            help = new int[row * col];
            sets = 0;
            for (int i = 0; i < board.length; i++) {
                for (int i1 = 0; i1 < board[i].length; i1++) {
                    if (board[i][i1] == '1') {
                        int index = index(i, i1);
                        parent[index] = index;
                        size[index] = 1;
                        sets++;
                    }
                }
            }
        }

        public int find (int i) {
            // 辅助数组,扁平化
            int hi = 0;
            while (i != parent[i]) {
                help[hi++] = i;
                i = parent[i];
            }
            // 这个过程要做路径压缩
            while (hi != 0) {
                help[hi--] = i;
            }
            return i;
        }

        public void union (int row, int col, int row1, int col1) {
            int i = index(row, col);
            int j = index(row1, col1);
            int i1 = find(i);
            int j1 = find(j);
            if (i1 != j1) {
                if (size[i1] >= size[j1]) {
                    parent[j1] = i1;
                    size[i1] += size[j1];
                } else {
                    parent[i1] = j1;
                    size[j1] += size[i1];
                }
                sets--;
            }
        }

        public int sets () {
            return sets;
        }


        private int index (int r, int c) {
            return r * col + c;
        }

    }


    public static class Node<V> {

        V value;

        public Node (V v) {
            value = v;
        }

    }

    public static class UnionFindDot<V> {
        public HashMap<V, Node<V>> nodes;
        public HashMap<Node<V>, Node<V>> parents;
        public HashMap<Node<V>, Integer> sizeMap;

        public UnionFindDot (List<V> list) {
            nodes = new HashMap<>();
            parents = new HashMap<>();
            sizeMap = new HashMap<>();
            for (V dot : list) {
                Node<V> node = new Node<>(dot);
                nodes.put(dot, node);
                parents.put(node, node);
                sizeMap.put(node, 1);
            }
        }

        public void union (V a, V b) {
            Node<V> af = findFather(nodes.get(a));
            Node<V> bf = findFather(nodes.get(b));
            if (af != bf) {
                int aSize = sizeMap.get(af);
                int bSize = sizeMap.get(bf);
                if (aSize >= bSize) {
                    parents.put(bf, af);
                    sizeMap.put(af, aSize + bSize);
                    sizeMap.remove(bf);
                } else {
                    parents.put(af, bf);
                    sizeMap.put(bf, aSize + bSize);
                    sizeMap.remove(af);
                }
            }
        }

        public int sets () {
            return sizeMap.size();
        }

        public boolean isSameSet (V a, V b) {
            return findFather(nodes.get(a)) == findFather(nodes.get(b));
        }

        public Node<V> findFather (Node<V> node) {
            Stack<Node<V>> path = new Stack<>();
            while (node != parents.get(node)) {
                node = parents.get(node);
                path.push(node);
            }
            while (!path.isEmpty()) {
                parents.put(path.pop(), node);
            }
            return node;
        }
    }

    public static class Dot {
    }
}
